﻿#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//qsort 使用举例
    //qsort函数是专门用来排序的函数，底层使用的是“快速排序”的方式
    //在调用该函数需要包含<stdlib.h>的头文件

    //void qsort(void* base,  //base是一个指针，指向的是待排序数组的第一个元素的地址，也就是数组名,就可以接收任意类型的地址
    //           size_t num,  //待排序数组的元素个数
    //           size_t size, //待排序数组中元素的大小,单位是字节
    //           int (*compar)(const void* p1, const void* p2) //compar是一个函数指针,这个指针可以接受一个函数地址
    //这个函数是使用qsort函数的人来设计的,这个函数是用来比较两个数组元素的大小
    //但是设计的这个函数的形式必须和上面的形式一样，就是两个形参是 const void* 类型，函数返回值类型是 int 类型
    //          );
    //qsort函数专门留下的第四个参数来传入一个实现两个数组元素比较的函数，目的就是实现不同类型的数组排序

//写一段代码使用qsort函数排序整型数据
//int cmp_int(const void* p1, const void* p2) //这个函数就是比较数组两个元素大小的函数，是使用者自己设计的
//{
//    //之前我们知道void* 类型的指针是无具体类型的指针，这种类型的指针是不能直接解引用也不能加减整数的运算
//    //所以我们需要通过强制类型转换，转换成我们需要的元素类型
//    if (*(int*)p1 > *(int*)p2)
//        return 1;
//    else if (*(int*)p1 == *(int*)p2)
//        return 0;
//    else return -1;
//}

    //但是qsort函数对使用者设计的*compar这个函数也有要求：
    //如果p1、p2指向的两个元素是前者大于后者 --> 函数返回值为>0
    //如果p1、p2指向的两个元素是前者等于后者 --> 函数返回值为=0
    //如果p1、p2指向的两个元素是前者小于后者 --> 函数返回值为<0

//int cmp_int(const void* p1, const void* p2)
//{
//    return *(int*)p1 - *(int*)p2; //这种写法更加简洁明了，表达的意思是一样的
//}  //qsort函数默认是升序的，如果想实现降序，则返回的值可以写成后者元素减去前者元素
//
//int main()
//{
//    int arr[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    qsort(arr, sz, sizeof(arr[0]), cmp_int);
//    //   base  num      size       *compar
//    for (int i = 0; i < sz; i++)
//    {
//        printf("%d ", arr[i]);
//    }
//	return 0;
//}

//写一段代码使用qsort函数排序结构体的数据
    //在排序结构体数据之前我们还要学习结构成员访问操作符中的结构体成员的间接访问
    //由于这个涉及到指针，当时还没接触指针所以跳过了
    //在学习间接访问之前，我们可以重新回顾一下结构体成员的直接访问是怎么实现的
//struct Stu
//{
//    char name[20];
//    int age;
//};
//int main()
//{
//    struct Stu s1 = { "zhangsan", 18 }; //定义结构体变量s1并初始化
//    printf("%s %d", s1.name, s1.age);//结构体成员的直接访问是通过点操作符（.）访问的。使用方式：结构体变量.成员名
//    return 0;
//}

    //有时候我们得到的不是一个结构体变量，而是得到了一个指向结构体的指针。
//struct Stu
//{
//    char name[20];
//    int age;
//};

//void Print(struct Stu* ps) //形参ps的类型是结构体指针类型(struct Stu*)
//{
//    //printf("%s %d", (*ps).name, (*ps).age); 
//    //将结构体指针ps解引用得到结构体再用点操作符（.）直接访问也可以实现，就和上述代码本质一样了，但这样较为麻烦
//    printf("%s %d", ps->name, ps->age);// -> 为结构体成员的间接访问操作符。使用方法：结构体指针->成员名
//
//}

//int main()
//{
//    struct Stu s2 = { "zhangsan", 18 }; //定义结构体变量s2并初始化
//    Print(&s2); //实参传递的是结构体变量s2的地址
//    return 0;
//}

    //有了上面的学习我们就可以排序结构体数据
//struct Stu
//{
//    char name[20];
//    int age;
//};
//
//    //这里的两个结构体元素怎么比较大小？
//    //1.如果按名字进行比较 --> 字符串比较 --strcmp函数
//    //2.如果按年龄进行比较 --> 整型比较 -- >/</==
//
//int cmp_name(const void* p1, const void* p2) //和之前一样，比较两元素大小函数的形参和返回值类型必须和qsort规定的保持一致
//{
//    return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
//    //和之前一样void*不能直接访问，需要强制类型转换成自己需要的类型
//    //通过查资料能知道strcmp函数的返回值和qsort函数规定的第四个参数*compar这个函数的返回值是一样的：
//    //如果p1、p2指向的两个字符串是前者大于后者 --> 函数返回值为>0
//    //如果p1、p2指向的两个字符串是前者等于后者 --> 函数返回值为=0
//    //如果p1、p2指向的两个字符串是前者小于后者 --> 函数返回值为<0
//}
//
//int cmp_age(const void* p1, const void* p2)
//{
//    return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age;
//}
//
//int main()
//{
//    struct Stu arr[3] = { {"zhangsan", 30}, {"lisi", 20}, {"wangwu", 18} };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    qsort(arr, sz, sizeof(arr[0]), cmp_name);//按名字进行比较
//    qsort(arr, sz, sizeof(arr[0]), cmp_age); //按年龄进行比较
//    return 0;
//}

//qsort函数的模拟实现
    //使用回调函数，模拟实现qsort(采用之前所学的冒泡的方式)。
    //实现的这个函数能像qsort函数一样排序任意类型的数据
    //注意：这里第一次使用 void* 的指针，先说明 void* 的作用：
    //void*的指针，是无具体类型的指针，虽然之前我们已经知道这种指针是不能直接解引用并且不能进行加减整数的运算
    //但是这种指针有一个好处就是它可以接收任意类型的地址，这为模拟实现qsort函数起到了直接作用
//先模拟实现qsort函数排序整型数据

void swap(char* p1, char* p2, size_t width) //实现任意类型两个元素的位置交换
{
    for (int i = 0; i < width; i++)
    {
        char p = *p1;
        *p1 = *p2;
        *p2 = p;
        p1++;
        p2++;
    }
}

int cmp_int(void* p1, void* p2) //这个函数就是针对整型数组排序的，如果是排序整型数组就调用该函数
{
    return *((int*)p1) - *((int*)p2);
}

int cmp_string(void* p1, void* p2)
{
    return strcmp(*(char*)p1, *(char*)p2);
}

void Bubble_sort(void* base, size_t sz, size_t width, int (*compar)(const void* p1, const void* p2))
    //在这个地方base这个形参为 void* 类型，目的就是为了能接收任意类型的数组而不仅仅是整型数组
    //而形参base调用的就是arr数组名，所以base就是数组首元素的地址

    //第二个形参为sz，是因为这个函数就是进行冒泡排序的，需要知道元素个数来进行多趟排序

    //第三个形参为width，作为自定义这个函数的我们，是并不知道使用这个函数传进来的数组是什么类型的
    //也就不知道数组里面元素是什么类型，width就是求出数组元素的大小，具体作用在后面代码里会着重讲解

    //第四个形参为int (*compar)(const void* p1, const void* p2)，是一个函数指针，
    //到这里会发现我们自定义的这个冒泡排序函数的形参和qsort函数的形参基本一致，因为我们就是在模拟qsort函数的实现逻辑
    //在qsort函数中第四个形参函数指针，返回的值则就决定两个元素是否交换位置
{
    for (int i = 0; i < sz - 1; i++) //排序的趟数
    {
        for (int j = 0; j < sz - i - 1; j++) //一趟所需要判断是否交换元素位置的次数
        {
            //if (compar(((int*)base) + j, ((int*)base) + j + 1) > 0)

            //在这里base由于是 void* 类型，是不能进行加减整数的运算，所以我们想到了将其强制类型转换成 int* 类型
            //这样有问题吗？其实在这里没有问题，但我们仔细想想，由于我们知道传过来的是整型数组所以想着直接转换成
            //int* 类型直接加1达到每次跳过一个元素比较大小，但如果传过来的不是整型数组呢？
            //那强制类型转换成 int* 类型是不是就有问题了，因为是 int* 类型，每次加1相当于是跳过4个字节，
            //而如果我们传过来的是 double 类型的元素，每次加1跳过4个字节，还能达到跳过下一个元素的目的吗，显然是不行的

            //我们再想想如果强制转换成 char* 类型呢
            //这样加1的话每次就是跳过1个字节，这样就有一个非常大的好处
            //就是我们可以通过加整数 width (即数组元素的大小)，来跳过 数组元素大小 个字节，就是这里形参 width 起到了作用
            //这样不管传过来的是什么类型的数组，由于可以通过sizeof求得元素大小，则跳过的字节数就能由 width 来控制

            if ( compar( ((char*)base)+j*width, ((char*)base)+(j+1)*width ) > 0 ) //交换两个元素位置
            {
                swap( ((char*)base) + j * width, ((char*)base) + (j + 1) * width, width);
                //这里尤其注意swap函数的两个实参是指针，并且类型是 char* 类型，所以定义这个函数时的形参也必须保持一致
                //由于数组元素的地址被强制类型转换成了 char* 类型，所以在解引用进行交换时只能得到1个字节的数据
                //如果数组本来不是char类型的，比如int类型，解引用后交换是不够的
                //还需要将后面得到的每一个字节数据都分别进行交换，才能达到两个元素进行交换的目的，在这里width也派上了用场
            }
        }
    }
}

int main()
{
    int arr[10] = { 9, 7, 5, 3, 1, 8, 6, 4, 2, 0 };
    int sz = sizeof(arr) / sizeof(arr[0]); //得到所要排序数组的元素个数，是用在冒泡排序里面
    Bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
    for (int i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}